/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/remove-duplicates-from-sorted-array
   @Language: C++
   @Datetime: 16-02-09 05:15
   */

// Method 1, erase, Time 789ms
class Solution {
public:
	/**
	 * @param A: a list of integers
	 * @return : return an integer
	 */
	/** Tips: The array is already sorted
	 * using two point i and j, i refers to last element,
	 * j refers current element.
	 * sketch :
	 * Array :  1   3   4   4   4   5  7
	 *     i____|   |___j
	 * Array :  1   3   4   4   4   5  7
	 *         i____|   |___j
	 * Array :  1   3   4   4   4   5  7
	 *             i____|   |___j
	 * Array :  1   3   4   4   4   5  7
	 *             i____|           |___j
	 *       copy j to i      
	 * Array :  1   3   4   5   4   5  7
	 *                 i____|       |___j
	 * Array :  1   3   4   5   7   5  7
	 *                     i____|      |___j
	 *
	 * At last,  erase all elements from i+i to end
	 *
	 * */
	int removeDuplicates(vector<int> &A) {
		// write your code here
		if (A.size()<1) return 0;
		vector<int>::iterator i,j;
		for(i=j=A.begin(); ++j!=A.end();)
			if (*j!=*i) *++i = *j;
		A.erase(++i,j);
		return A.size();
	}
};


// Method 2, replace, Time 786ms
class Solution {
public:
	/**
	 * @param A: a list of integers
	 * @return : return an integer
	 */
	int removeDuplicates(vector<int> &nums) {
		// write your code here
		if(nums.size()==0) return 0;
		int len=1;
		for(int i=1; i<nums.size(); ++i)
			if(nums[i-1]!=nums[i]) nums[len++]=nums[i];
		return len;
	}
};
